\section{Fermat-Euler 定理}


\begin{frame}{Fermat 小定理、Euler定理、Wilson定理}
  \begin{theorem}%定理1
    [Fermat 小定理， Fermat's little theorem]
    设 $p$ 为素数， $p \nmid a$ ($a$ 为整数), 则
  \[
    a^{p-1} \equiv 1 \quad\left(\mod p\right).
\]
（也可叙述为： $a^{p} \equiv a\left(\mod p\right)$, 对任意整数 $a$.)
\end{theorem}


%\begin{proof}[证法 1]
%  对 $a$ 用数学归纳法。 $a=1$ 时显然成立。 设 $a^{p} \equiv a\left(\mod p\right)$ 成立。考察
%\[
%(a+1)^{p}=a^{p}+\cdots+\mathrm{C}_{p}^{k} a^{k}+\cdots+1, \quad \mathrm{C}_{p}^{k}=\frac{p(p-1) \cdots(p-k+1)}{k!}
%\]
%$\mathrm{C}_{p}^{k}$ 是整数， 是 $p$ 的倍数 (分子的 $p$ 不可能被分母消去， 因 $0<k<p$ ), 故
%\[
%  \begin{aligned}
%    (a+1)^{p} & \equiv a^{p}+0+\cdots+0+\cdots 0+1 \\
%  & \equiv a^{p}+1 \equiv a+1 \quad\left(\mod p\right)
%\end{aligned}
%\]
%\end{proof}
\pause
\begin{proof*}[证法 2]
  记 $\Phi_{p}=\{1,2, \cdots, p-1\}$. 
  设 $p \nmid a$, 令
\[
  a \Phi=\{1 \cdot a, 2 \cdot a, \cdots,(p-1) \cdot a\}.
\]
    那么 $a \Phi$ 与 $\Phi$ 中的元素模 $p$ 相同 (由上节引理 1). 
    将 $a \Phi$ 与 $\Phi$ 中的元素各自乘起来， 得
\[
  \begin{aligned}
    (a) \cdot(2 a) \cdots(p-1) a &\equiv 1 \cdot 2 \cdots(p-1) \quad\left(\mod p\right), \\
    a^{p-1}(p-1)!& \equiv(p-1)!\quad\left(\mod p\right), \\
    a^{p-1} & \equiv 1 \quad\left(\mod p\right).
\end{aligned}
\]
\pause
例如， $p=5$ 时， $2$ 的 $1$-$4$ 次幂为 $2,4,3,1\left(\mod 5\right)$.
\end{proof*}

\end{frame}
\begin{frame}%{Euler 定理}

  \begin{theorem}%定理2
    [Euler 定理] 设整数 $a$ 与 $m$ 互素， 则
  \[
    a^{\varphi(m)} \equiv 1 \quad\left(\mod m\right),
\]
其中 $\varphi$ 是 Euler 函数，即 $\varphi(m)$ 是 “小于 $m$ 且与 $m$ 互素”的正整数个数。
\end{theorem}

\pause
\begin{proof}
 记 $\Phi_{m}=\left\{k_{1}, \cdots, k_{\varphi(m)}\right\}$ 是 “小于 $m$ 且与 $m$ 互素” 的正整数集合。 
\pause
 令
 \[
   a \Phi_{m}=\left\{a k_{1}, \cdots, a k_{\varphi(m)}\right\},
 \]
 则 $a \Phi_{m}$ 与 $\Phi_{m}$ 的元素模 $m$ 同余 (上节引理 1). 
\pause
 将每个集合的元素各自乘起来，得到
 \[
   \begin{aligned}
     a k_{1} \cdot a k_{2} \cdots a k_{\varphi(m)} & \equiv k_{1} \cdot k_{2} \cdots k_{\varphi(m)} \quad\left(\mod m\right), \\
     \pause
     a^{\varphi(m)} & \equiv 1 \quad\left(\mod m\right).
 \end{aligned}
 \]
 （因 $k_{1}, \cdots, k_{\varphi(m)}$ 与 $m$ 互素， 可以约化去).
 \end{proof}
 \end{frame}

 \begin{frame}%{Wilson 定理}

   \begin{theorem}%定理3
     \color{gray}
   (1) 设 $p$ 为素数， 则 $\mathbb{F}_{p}=\mathbb{Z} / p \mathbb{Z}=\{\overline{0}, \overline{1}, \cdots, \overline{p-1}\}$ 的元素恰为多项式 $X^{p}-X$ 的 $p$ 个根， 即%
   \footnote{一般的域$F$ (包括有限域) 上的一元多项式环$F[X]$的理论大部分与数域上的相同，
   参见[张贤科-许甫华，高等代数学]. 不过注意有不同的地方，尤其是特征大于$0$和特征$0$有不同的地方。}
 \[
   X^{p}-X = X(X-\overline{1})(X-\overline{2}) \cdots[X-(\overline{p-1})],
 \]
 \pause
 或者说， 非零元集 $\mathbb{F}_{p}^{*}$ 恰为 $X^{p-1}-\overline{1}$ 的 $p-1$ 个根：
 \[
   X^{p-1}-\overline{1} = (X-\overline{1}) \cdots[X-(\overline{p-1})].
 \]

 \pause
  (2) (Wilson(威尔逊) 定理) $p$ 为素数当且仅当
\[
  (p-1)!\equiv-1 \quad\left(\mod p\right).
\]
\end{theorem}

\pause
\begin{proof}
\color{gray}
 (1) 设 $\bar{a} \in \mathbb{F}_{p}$, 则 $\overline{a^{p}}=\bar{a}$ (Fermat 小定理), 
 故 $\bar{a}$ 是 $X^{p}-X$ 的根。 $\bar{a} \in \mathbb{F}_{p}$共 $p$ 个取值， 故 $X^{p}-X = X(X-\overline{1})(X-\overline{2}) \cdots[X-\overline{(p-1)}]$.

 (2) 对 $X^{p-1}-\overline{1} = (X-\overline{1}) \cdots[X-(\overline{p-1})]$, 
 令 $X=0$ 则得 Wilson 的等式 (分$p=2$和$p>2$讨论下)。 反之， 设
 \[
 (p-1)!\equiv-1 \quad\left(\mod p\right)
 \]
 则对任意 $d \mid p$ 有 $(p-1)!\equiv-1\left(\mod d\right)$. 若 $d<p$ 则此式化为 $0 \equiv-1\left(\mod d\right)$, 则 $d=1$. 这说明 $p$ 的因子只有 $1$ 和 $p$, 故 $p$ 为素数。
 \end{proof}


 \end{frame}

 \begin{frame}
 \begin{explain*}%说明
   Fermat 小定理可用于素数检验：若有整数 $a$ 使得 $a^{p} \nequiv a\left(\mod p\right)$,则 $p$ 不是素数。 例如 $3^{10}=3^{4 \cdot 2} \cdot 3^{2} \equiv 3^{2} \nequiv 3\left(\mod 10\right)$, 故 $10$ 不是素数 (事实上，由 Euler 定理， $3^{4}=3^{\varphi(10)} \equiv 1\left(\mod 10\right)$).
 \end{explain*}

\pause
Euler 定理有许多应用， 特别著名的是在 RSA 加密算法上的应用。 现代社会中信息加密日显重要。 1974-1976 年， 多人提出“公开密钥”体制， 即加密密钥可以公开 (从而可允许很多人将信息加密传送), 但 “由加密密钥 (公钥) 推导出解密密钥 (私钥) 在现实计算中不可行” (因此外人无法对加密信息解密解读). 其诀窃是运用一种 “单向函数”, 即\emph{正向易算， 反向难行}。人们最先想到的 (准) 单向函数就是乘积一分解， 即计算乘积容易， 但对极大整数进行因子分解很难行。 据此， 1977 年首先诞生了著名的 RSA 加密算法， 由美国的 Rivest （里夫斯特）, Shamir(沙米尔), Adleman(阿德莱曼)提出， 被广泛应用。

在 RSA 加密算法中， 首先选取大素数 $p, q$, 乘之得到 $N=p q$. 将原信息 $a$ (表示为整数， 与 $N$ 互素)加密的方法是：对固定的 $e$ (与 $\varphi(N)$ 互素), 求
\[
  b \equiv a^{e} \quad\left(\mod N\right).
\]
$b$ 即为加密后的信息， 可以传输和储存。 加密密钥 $e$ 和 $N$ 都可以公开 (公钥)。
解密密钥 $d$ (私钥) 当然应当是
\[
  d=e^{-1} \quad\left(\mod \varphi(N\right)),\quad\text{ 即 }\quad e d \equiv 1 \quad\left(\mod \varphi(N\right)),
\]
因为显然
\[
  b^{d} \equiv a^{e \cdot e^{-1}} \equiv a \quad\left(\mod N\right).
\]
注意 $e$ 和 $d=e^{-1}$ 是模 $\varphi(N)$ 定义的， 因为由 Euler 定理知 $a^{\varphi(N)} \equiv 1\left(\mod N\right)$. 破密过程常被称为离散对数问题 (discrete logarithm problem).
\end{frame}

\begin{frame}
 注意， 外人虽然知道公钥 ($e$ 和 $N$), 但难以求出私钥 $d=e^{-1}$ (从而解读加密信息), 因为 $\varphi(N)$ 不易求， 只有在知道因子分解 $N=p q$ 时才易求， 而极大整数因子分解很难。

（说明：至今无人证明因子分解 $N$ 是唯一的解密方法， 但从未见有更好的方法。 
 2009 年 12 月， $232$ 位数的 $N$ 被成功分解。 分布式计算和量子计算机对 RSA 算法提出挑战。)

 RSA 算法之外， 已发现 ECC (椭圆曲线算法) 等更好的加密算法。

 \begin{comment*}%评述
 Fermat 小定理和 Euler 定理， 给出了模算术中数幂的最小周期。 数幂到此周期必须返还归一。 这是模算术与自然数运算的最大不同。 一个自然数的幂可以无限大下去(因此称自然数是自由的). 此二定理是原根和循环群等理论的发端， 在数字化信息等有重要应用。 论数者单赞这 Fermat 小定理和 Euler 定理的妙处曰：
 \begin{poem}
 费马欧拉定大限， 连翻筋斗至此还。\\
 虽然心猿不自在，却得轮回真腣传。
 \end{poem}
 \end{comment*}\end{frame}

 \begin{frame}{小结}
   \begin{enumerate}
     \item 叙述Fermat小定理、Euler定理、Wilson定理。
     \item 举例说说Euler定理的应用。
   \end{enumerate}
 \end{frame}
